// Main Class //
////////////////
class HuffmanCodecDemo implements Runnable {
	def void run() {
		// Implemenation of the sample described here:
		// http://en.wikipedia.org/wiki/Huffman_coding
		
		// Demo1
		def input = ("A" * 40) + ("B" * 35) + ("C" * 20) + ("D" * 5)
		//new FileOutputStream("input.txt").withWriter { out-> out.println(input) }
		def codec = new HuffmanCodec(input)
		def tree = codec.codeTree
		tree.dumpTree()
		tree.dumpCodeTable()
		
		// Demo2
		//def input = ("A" * 40) + ("B" * 35) + ("C" * 20) + ("D" * 5)
		//def codec = new HuffmanCodec(input)
		//println(codec.encode(input))
		
	}
}

// Supporting Classes //
////////////////////////

/** Simple Huffman codec that takes all input into memory. Using simple String as input */
class HuffmanCodec {
	HuffmanCodeTree codeTree
	
	HuffmanCodec(String input) {
		def inputSymbols = generateSymbols(input)
		codeTree = buildHuffmanTree(inputSymbols)
	}	
	String encode(String input) {
		def inputSymbols = generateSymbols(input)
		encode(inputSymbols)
	}	
	
	protected List<Symbol> generateSymbols(String input) {
		input.collect { ch -> 
			def sym = new Symbol()
			sym.value = ch
			sym
		}		
	}
				
	protected String encode(List<Symbol> inputSymbols) {
		def sb = new StringBuilder()
		def codeTable = codeTree.codeTable
		inputSymbols.each { sym -> sb.append(codeTable[sym].code) }
		sb.toString()
	}	
	protected HuffmanCodeTree buildHuffmanTree(List<Symbol> inputSymbols) {
		def symbolFreqs = generateSymbolFrequencies(inputSymbols)
		def tree = new HuffmanCodeTree(symbolFreqs)
		tree
	}	
	protected Map<Symbol, Integer> generateSymbolFrequencies(List<Symbol> symbols) {
		Map<Symbol, Integer> freq = [:]
		symbols.each { sym ->
			def count = freq[sym]
			if (count == null) { count = 0 }
			count += 1
			freq[sym] = count
		}		
		freq
	}
}
class Symbol {
	Object value
	String toString() { value.toString() }
	int hashCode() { value.hashCode() }
	boolean equals(Object that) { this.value.equals(that.value) }
}
class Node {
	int weight // frequency of the symbol appearance
	Node parent
	String code
}
class LeafNode extends Node {
	Symbol sym
	String toString() {	"L($sym,$weight,$code)" }
}
class InternalNode extends Node {
	Node leftChild   // 0's
	Node rightChild  // 1's	
	String toString() {	"I($weight,$code,$leftChild,$rightChild)" }
}
class HuffmanCodeTree {
	private InternalNode root
	private Map<Symbol, LeafNode> codeTable
		
	public HuffmanCodeTree(Map<Symbol, Integer> symbolFreqs) {
		codeTable = [:]
		buildTree(symbolFreqs)
	}
	String toString() {	root.toString() }
	Map<Symbol, LeafNode> getCodeTable() { codeTable }
	void dumpCodeTable() {
		codeTable.each { sym, node -> println("$sym, $node.code") }
	}
	void dumpTree() {
		walkTree(root, 0) { parent, rightNode, leftNode, depth ->
			print(' ' * depth)
			println("I($parent.weight,$parent.code)")
			if (rightNode != null) {
				print(' ' * depth)
				def sym = rightNode instanceof LeafNode ? "$rightNode.sym," : ""
				println("+->Right(" + sym + "$rightNode.weight,$rightNode.code)")
			}
			if (leftNode != null) {
				print(' ' * depth)
				def sym = leftNode instanceof LeafNode ? "$leftNode.sym," : ""
				println("+->Left(" + sym + "$leftNode.weight,$leftNode.code)")
			}
		}
	}
	
	private void buildTree(Map<Symbol, Integer> symbolFreqs) {
		symbolFreqs.each { sym, freq -> 
			def leaf = new LeafNode()
			leaf.sym = sym
			leaf.weight = freq
			codeTable[sym] = leaf
		}
		def processingNodes = codeTable.values().toList()
		processingNodes.sort { a, b -> b.weight - a.weight }
		def node1 = processingNodes.pop()
		while (processingNodes.size() > 0 ) {
			def node2 = processingNodes.pop()
			def parent = new InternalNode()
			parent.rightChild = node1
			parent.leftChild = node2
			parent.weight = node1.weight + node2.weight
			node1.parent = parent
			node2.parent = parent
			// Reset and prepare for next loop
			node1 = parent
		}
		// Final node1 is the root
		root = node1
		buildCode()
	}
	private void buildCode() {
		root.code = ""
		walkTree(root, 0) { parent, rightNode, leftNode, depth ->
			if (rightNode != null) {
				rightNode.code = parent.code + "1"
			}
			if (leftNode != null) {
				leftNode.code = parent.code + "0"
			}
		}
	}	
	private void walkTree(InternalNode parent, Integer depth, Closure closure) {
		Node rightNode = parent.rightChild
		Node leftNode = parent.leftChild
		closure.call(parent, rightNode, leftNode, depth)
		if (rightNode instanceof InternalNode) {
			walkTree(rightNode, depth + 1, closure)
		}
		if (leftNode instanceof InternalNode) {
			walkTree(leftNode, depth + 1, closure)
		}
	}
}